//
//  206_反转链表.swift
//  Algorithm
//
//  Created by 陈志强 on 2021/8/5.
//

/*
 提示：

 链表中节点的数目范围是 [0, 5000]
 -5000 <= Node.val <= 5000
  

 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/reverse-linked-list
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import Foundation

class Solution_206 {
    // 两个指针的方案
    func reverseList(_ head: ListNode?) -> ListNode? {
        var preNode:ListNode? = nil
        var curNode = head
        
        while ((curNode?.next) != nil)  {
            let next = curNode?.next
            
            curNode?.next = preNode
            preNode = curNode
            curNode = next
        }
        
        return curNode
    }
    
    func reveraseNewList(_ head: ListNode?) -> ListNode? {
        //递归终止条件
        if head==nil,head?.next==nil {
            return head
        }
        
        //递归
        reverseList(head?.next)
        
        //递归逻辑
        head?.next?.next = head
        head?.next = nil

        //清除上下文相关
        
        return head
    }
}
